public class Test3 {
    /**
     * 计数排序：
     * 时间复杂度：O(N)
     * 空间复杂度：O(M) M:代表 当前数据的范围900 - 999
     * 稳定性：当前代码是不稳定的，但是本质是稳定的
     *
     * 一般适用于 有n个数，数据范围是0-n之间的
     * @param array
     */
    public static void countingSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //说明，已经找到了最大值和最小值
        int[] count = new int[maxVal-minVal+1];//默认都是0
        //统计array数组当中，每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            //为了空间的合理使用 这里需要index-minVal  防止923-900
            count[index-minVal]++;
        }
        //说明，在计数数组当中，已经把array数组当中，每个数据出现的次数已经统计好了
        //接下来，只需要，遍历计数数组，把数据写回array
        int indexArray = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //这里一定要加minVal，因为不一定就是i出现了count[i]
                array[indexArray] = i+minVal;
                count[i]--;//拷贝一个之后，次数也就少一个
                indexArray++;//下标得向后移动
            }
        }
    }
}
